home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Utilities / Winter Shell 1.0d2 / Source / Libraries / PointerFixedLib / PointerFixedLib.c next >
Encoding:
C/C++ Source or Header  |  1994-01-20  |  10.9 KB  |  291 lines  |  [TEXT/KAHL]
  1. /* allocate pointers of fixed size
  2.     94/01/20 aih - when a pointer is disposed of all blocks that belong to
  3.                         that pointer are removed from the free list
  4.     94/01/17 aih - added list of pointers allocated from system, so can
  5.                         return free'd pointers to the system
  6.     94/01/07 aih - changed allocated block header to point to the free list
  7.                         instead of the block size, which makes disposal more efficient
  8.                         and the size can still be derived from the free list's block
  9.                         sizes.
  10.                      -    improved data validation
  11.     94/01/02 aih - created */
  12.  
  13. #include "LLPtrLib.h"
  14. #include "MemoryLib.h"
  15. #include "PointerFixedLib.h"
  16.  
  17. /* Maximum size of pointers to allocate from system. Some memory allocators
  18.     are optimized for pointer sizes that are powers of two, and may round
  19.     up memory requests to the nearest power of two. Therefore, it's a good
  20.     idea (though not required) to use a power of two as the pointer size. */
  21. #define MAXPTR    (4096)
  22.  
  23. /*----------------------------------------------------------------------------*/
  24. /* fixed-sized pointer allocation routines */
  25. /*----------------------------------------------------------------------------*/
  26.  
  27. typedef struct FreeListStruct FreeListType;
  28.  
  29. /* Header of a pointer allocated from the system, used so we can return
  30.     the pointers to the system's memory pool. A reference count keeps track
  31.     of how many blocks are allocated from the pointer. When the reference
  32.     count reaches zero the pointer is disposed of. This means that allocating
  33.     a small number of blocks and then soon after disposing of them would
  34.     be fairly inefficient, since the pointer would be allocated and then
  35.     disposed of; it would be better to allocate many blocks and then
  36.     dispose of them altogether. */
  37. typedef struct {
  38.     FreeListType *freelist;    /* free list that owns this pointer */
  39.     short refcnt;                /* number of blocks allocated from this pointer */
  40.     short nblocks;                /* number of blocks this pointer can contain (for debugging) */
  41.     short blksz;                /* size of blocks allocated from this pointer (for debugging) */
  42.     /* ... remainder of pointer divided into blocks ... */
  43. } SystemPointerType;
  44.  
  45. /* Header of a block allocated with this library. By having the block header
  46.     of an allocated block point to the pointer from which the block was
  47.     allocated we can quickly insert the block back into the free list when
  48.     the block is disposed of. Disposal of the pointer when the reference
  49.     count reaches zero is also made reasonably efficient, since we have direct
  50.     access to the pointer. */
  51. typedef struct  {
  52.     SystemPointerType *sysptr;    /* pointer from which block was allocated */
  53.     /* ... remainder of block contains data for use by application ... */
  54. } BlockAllocType;
  55.  
  56. /* Header of a free block allocated with this library. The free block header
  57.     is 8 bytes, while the allocated block header is only 4 bytes. This means
  58.     that the overhead of a block allocated with this library is only 4 bytes,
  59.     though the minimum size of blocks is 8 bytes since they must be at least
  60.     large enough to contain the free block header (smaller blocks can still
  61.     be allocated by the application, but they'll be rounded up to 8 bytes).
  62.     We maintain a linked list of free blocks. When a block is allocated,
  63.     it is removed from the free list and its header is converted to the
  64.     header of an allocated block (see above). When a block is freed it is
  65.     inserted into the free list and its header is converted to the header
  66.     of a free block. By maintaining access to the pointer from which the block
  67.     was allocated we can quickly decrement the reference count of the pointer,
  68.     and when the reference count reaches zero we can dispose of the pointer. */
  69. typedef struct  {
  70.     LLType next;                    /* next free block */
  71.     SystemPointerType *sysptr;    /* pointer from which block was allocated */
  72.     /* ... remainder of block is reserved for future allocation ... */
  73. } BlockFreeType;
  74.  
  75. /* For calculating the minimum size of a block, we need the maximum of
  76.     the size of an allocated block header and a free block header. This
  77.     is easily accomplished by placing the structures into a union, with
  78.     the property
  79.         sizeof(BlockType) == max(sizeof(BlockAllocType), sizeof(BlockFreeType))
  80.     We only use this union for calculating a block's size. */
  81. typedef union {
  82.     BlockAllocType alloc;
  83.     BlockFreeType free;
  84. } BlockType;
  85.  
  86. /* List of free blocks. A separate list is maintained for each unique
  87.     block size. */
  88. struct FreeListStruct {
  89.     LLType next;                    /* next free list */
  90.     short blksz;                    /* size of blocks */
  91.     BlockFreeType *free;            /* first free block */
  92. };
  93.  
  94. /* true if a valid pointer allocated from the system */
  95. static Boolean SystemPointerValid(SystemPointerType *sysptr)
  96. {
  97.     if (! PtrValidSize(sysptr, sizeof(SystemPointerType))) return(false);
  98.     if (sysptr->nblocks < 0) return(false);
  99.     if (sysptr->blksz < sizeof(BlockType)) return(false);
  100.     if (sysptr->blksz != sysptr->freelist->blksz) return(false);
  101.     if (sysptr->refcnt < 0 || sysptr->nblocks < sysptr->refcnt) return(false);
  102.     if (PtrSize(sysptr) != sysptr->nblocks * sysptr->blksz + sizeof(SystemPointerType)) return(false);
  103.     if (sysptr->nblocks * sysptr->blksz + sizeof(SystemPointerType) > MAXPTR) return(false);
  104.     return(true);
  105. }
  106.  
  107. /* true if a valid free list */
  108. static Boolean FreeListValid(FreeListType *list)
  109. {
  110.     if (! PtrValidSize(list, sizeof(FreeListType))) return(false);
  111.     if (list->blksz < 0 || MAXPTR < list->blksz) return(false);
  112.     return(true);
  113. }
  114.  
  115. /* find free list with items of specified size, create new list if needed */
  116. static FreeListType *FreeListFind(size_t blksz)
  117. {
  118.     static FreeListType *free_lists;
  119.     register FreeListType *list, *prev;
  120.     
  121.     /* find free list */
  122.     prev = NULL;
  123.     for (list = free_lists; list; list = LLPNext(list)) {
  124.         if (list->blksz == blksz)
  125.             break;
  126.         prev = list;
  127.     }
  128.     if (! list) {
  129.         /* create new list */
  130.         free_lists = LLPInsert(free_lists, PtrBeginClear(sizeof(FreeListType)));
  131.         free_lists->blksz = blksz;
  132.     }
  133.     else if (list != free_lists) {
  134.         /* move found list to front */
  135.         free_lists = LLPInsert(LLPDeleteFast(free_lists, list, prev), list);
  136.     }
  137.     ensure(FreeListValid(free_lists) && free_lists->blksz == blksz);
  138.     return(free_lists);
  139. }
  140.  
  141. /* allign and adjust size to be a valid block size, including the block header */
  142. static size_t AdjustSize(size_t size)
  143. {
  144.     require(0 < size);
  145.     require(size <= MAXPTR - sizeof(BlockType) - sizeof(SystemPointerType) - 1);
  146.     if ((size & 0x01) != 0)
  147.         size++;
  148.     size += sizeof(BlockAllocType);
  149.     if (size < sizeof(BlockType))
  150.         size = sizeof(BlockType);
  151.     ensure(sizeof(BlockType) <= size && size <= MAXPTR - sizeof(SystemPointerType));
  152.     return(size);
  153. }
  154.  
  155. /* true if a valid fixed-size pointer */
  156. Boolean PtrFixedValid(void *p)
  157. {
  158.     BlockAllocType *blockalloc;
  159.     
  160.     if (! MemValid(p)) return(false);
  161.     blockalloc = &((BlockAllocType *) p)[-1];
  162.     if (! SystemPointerValid(blockalloc->sysptr)) return(false);
  163.     if (blockalloc->sysptr->refcnt == 0) return(false);
  164.     return(true);
  165. }
  166.  
  167. /* True if a valid pointer of 'size' bytes. This differs from PtrValidSize,
  168.     which only requires that a pointer be at least 'size' bytes long. The
  169.     difference is due to the fixed size of pointers allocated wtih this
  170.     library. */
  171. Boolean PtrFixedValidSize(void *p, size_t size)
  172. {
  173.     /* check pointer */
  174.     if (! PtrFixedValid(p)) return(false);
  175.     if (((BlockAllocType *) p)[-1].sysptr->blksz != AdjustSize(size)) return(false);
  176.     return(true);
  177. }
  178.  
  179. /* Allocate a fixed-size pointer. The pointer is word-alligned. */
  180. void *PtrFixedBegin(size_t blksz)
  181. {
  182.     FreeListType *list;            /* free list from which to allocate a block */
  183.     BlockFreeType *blockfree;    /* block header for free block */
  184.     BlockAllocType *blockalloc;/* block header for allocated block */
  185.     
  186.     /* get free list for blocks of requested size */
  187.     blksz = AdjustSize(blksz);
  188.     list = FreeListFind(blksz);
  189.     
  190.     /* allocate new pointer if no free blocks of requested size */
  191.     if (! list->free) {
  192.         SystemPointerType *sysptr; /* pointer allocated from system */
  193.         short nblocks;    /* number of blocks to allocate */
  194.         short nbytes;    /* number of bytes to allocate */
  195.         char *p;            /* pointer allocated from system */
  196.         
  197.         /* Allocate a pointer from the system to contain as many items of
  198.             the requested size as will fit in MAXPTR bytes. By calling
  199.             StripAddress here we can safely do address arithmetic on all
  200.             pointers without having to call StripAddress anywhere else. */
  201.         nblocks = (MAXPTR - sizeof(SystemPointerType)) / blksz;
  202.         nbytes = nblocks * blksz + sizeof(SystemPointerType);
  203.         p = StripAddress(PtrBegin(nbytes));
  204.         sysptr = (SystemPointerType *) p;
  205.         memclr(sysptr, sizeof(SystemPointerType));
  206.         
  207.         /* Initialize system pointer's header. For debugging, we keep track of
  208.             the size of blocks allocated from this pointer and of how many blocks
  209.             can be allocated from this pointer. */
  210.         sysptr->freelist = list;
  211.         sysptr->nblocks = nblocks;
  212.         sysptr->blksz = blksz;
  213.         
  214.         /* divide pointer into blocks and join them into a linked list */
  215.         p += sizeof(SystemPointerType);
  216.         while (nblocks-- > 0) {
  217.             list->free = LLPInsert(list->free, p);
  218.             ((BlockFreeType *) p)->sysptr = sysptr;
  219.             p += blksz;
  220.         }
  221.     }
  222.     
  223.     /* remove a block from the free list */
  224.     blockfree = list->free;
  225.     list->free = LLPDelete(list->free, blockfree);
  226.     
  227.     /* Set block header for an allocated block. By having the block header
  228.         point to the pointer from which the block was allocated we can quickly
  229.         dispose of the block. */
  230.     blockalloc = (BlockAllocType *) blockfree;
  231.     blockalloc->sysptr = blockfree->sysptr;
  232.     blockfree = NULL;
  233.     
  234.     /* increment reference count for pointer */
  235.     check(blockalloc->sysptr->refcnt < blockalloc->sysptr->nblocks);
  236.     blockalloc->sysptr->refcnt++;
  237.     
  238.     ensure(PtrFixedValidSize(blockalloc + 1, blksz - sizeof(BlockAllocType)));
  239.     return(blockalloc + 1);
  240. }
  241.  
  242. /* dispose of a fixed-size pointer */
  243. void PtrFixedEnd(void *p)
  244. {
  245.     FreeListType *list;                /* free list from which block was allocated */
  246.     SystemPointerType *sysptr;        /* pointer from which block was allocated */
  247.     BlockFreeType *blockfree;        /* block header for free block */
  248.     BlockAllocType *blockalloc;    /* block header for allocated block */
  249.     
  250.     require(! p || PtrFixedValid(p));
  251.     if (p) {
  252.  
  253.         /* convert block to a free block */
  254.         blockalloc = (BlockAllocType *) p - 1;
  255.         p = NULL;
  256.         sysptr = blockalloc->sysptr;
  257.         list = sysptr->freelist;
  258.         blockfree = (BlockFreeType *) blockalloc;
  259.         blockalloc = NULL;
  260.         
  261.         /* insert block into its free list */
  262.         list->free = LLPInsert(list->free, blockfree);
  263.         blockfree->sysptr = sysptr;
  264.         
  265.         /* decrement reference count of pointer containing block; dispose
  266.             of pointer when reference count reaches zero */
  267.         check(sysptr->refcnt > 0);
  268.         if (--sysptr->refcnt == 0) {
  269.             BlockFreeType *prev, *next;
  270.  
  271.             /* remove all blocks that belong to this pointer from the free list */
  272.             /* program_note: this may make block disposal inefficient if there
  273.                 are many blocks (e.g., in the thousands or tens of thousands) */
  274.             prev = NULL;
  275.             blockfree = list->free;
  276.             while (blockfree) {
  277.                 next = LLPNext(blockfree);
  278.                 if (blockfree->sysptr == sysptr)
  279.                     list->free = LLPDeleteFast(list->free, blockfree, prev);
  280.                 else
  281.                     prev = blockfree;
  282.                 blockfree = next;
  283.             }
  284.             
  285.             /* dispose of pointer */
  286.             PtrEnd(sysptr);
  287.         }        
  288.     }
  289.     ensure(! PtrFixedValid(p));
  290. }
  291.